from typing import List

class Solution:
    def __init__(self):
        self.count = 0
    
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        """
        回溯算法解决目标和问题
        遍历所有可能的表达式，计算结果等于target的表达式数目
        
        时间复杂度：O(2^n)，其中n是数组nums的长度
        空间复杂度：O(n)，递归调用的栈空间
        
        Args:
            nums: 非负整数数组
            target: 目标和
            
        Returns:
            不同表达式的数目
        """
        self.count = 0
        self.backtrack(nums, target, 0, 0)
        return self.count
    
    def backtrack(self, nums: List[int], target: int, index: int, current_sum: int):
        """
        回溯函数
        
        Args:
            nums: 数组
            target: 目标值
            index: 当前处理的数组索引
            current_sum: 当前累计和
        """
        if index == len(nums):
            if current_sum == target:
                self.count += 1
        else:
            # 添加正号
            self.backtrack(nums, target, index + 1, current_sum + nums[index])
            # 添加负号
            self.backtrack(nums, target, index + 1, current_sum - nums[index])
